#include <vector>
#include <iostream>

using namespace std;

int main()
{
    int t;
    cin >> t;
    for (int tt = 0; tt < t; tt++)
    {
        float P; cin >> P;
        P = 1 - P; // >= P
        int N; cin >> N;
        vector<int> val(N);
        vector<float> prob(N);
        int sum = 0;
        for (int i = 0; i < N; i++)
        {
            cin >> val[i] >> prob[i];
            prob[i] = 1 - prob[i];
            sum += val[i];
        }
        
        vector<float> dp(sum + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < N; i++)
            for (int j = sum; j >= val[i]; j--)
                dp[j] = max(dp[j], dp[j - val[i]] * prob[i]);

        for (int i = sum; i >= 0; i--)
            if (dp[i] >= P)
            {
                cout << i << endl;
                break;
            }
    }
}
/*
1
0.04 3
1 0.02
2 0.03
3 0.05

*/